<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>单向链表</title>
</head>
<body>
    <script>
        /* 链表的常见方法
            1.append(element):向链表尾部添加一个新的项
            2.insert(position,element):向向链表的特定位置插入一个新的项
            3.get(position):获取对应位置的元素
            4.indexOf(element):返回元素在链表中的索引,如果元素中没有该索引则返回-1
            5.update(position,element):修改某个位置的元素
            6.removeAt(posotion):从链表的特定位置移除一项
            7.remove(element):从链表中移除一项
            8.isEmpty():如果链表中不包含元素返回true,否则返回false
            9.size():返回链表的长度
            10.toString():格式化输入链表的值

        */
        class LinkedList{
            head = null;
            length = 0;

            //1.append():追加节点到最后的方法
            append(data){
                //创建新添加的节点
                let newNode = new Node(data);
                
                //判断是否为第一个节点
                if(this.length == 0){ //是第一个节点
                    //把第一个节点赋值给head
                    this.head = newNode;
                }else{                //不是第一个节点
                    //找到最后一个节点
                    let current = this.head;
                    while(current.next){
                        current = current.next;
                    }
                    //把新节点赋值给最后一个节点的指针
                    current.next = newNode;
                }
                //链表增加一个长度
                this.length += 1;
            }

            //2.insert(position,element):向向链表的特定位置插入一个新的项
            insert(position,element){
                //边界值判断,不合法的位置需要直接终止
                if(position < 0 || position > this.length) return false;

                //先创建新的节点
                let newNode = new Node(element);

                //如果插入到第一个位置
                if(position === 0){
                    //先把新node的next的值赋为原来那个node(因为原来的node变成最后了)
                    newNode.next = this.head;
                    //把head指向新node
                    this.head = newNode;
                }else{ //插入到任意位置(包含了插入到最后的情况)
                    //定义标记,控制循环次数
                    let index = 0;
                    //定义变量更新当前节点
                    let current = this.head;
                    //定义变量用来保存更新前的节点
                    let pre = null;
                    //循环查找插入的位置
                    while(index++ < position){
                        //保存更新前的节点
                        pre = current;
                        //更新当前节点
                        current = current.next;
                    }
                    newNode.next = current;
                    pre.next = newNode;
                }
                this.length += 1;
                return true;
            }

            //理解上面俩个方法的话,其它方法其实很简单了
            //3.get():根据位置获取数据
            get(position){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                //获取当前节点
                let current = this.head;
                let index = 0;
                //如果index等于position的时候则代表找了,就停止
                while(index++ < position){
                    current = current.next;
                }
                //返回找到的值
                return current.data;
            }

            //4.indexOf(element):根据值获取值对应的下标
            indexOf(data){
                let current = this.head;
                let index = 0;
                //遍历条件为所有节点
                while(current){
                    //当前节点等于传入的值,就返回对应的下标
                    if(current.data === data){
                        return index;
                    }
                    //更新当前节点和当前节点对应的下标
                    current = current.next;
                    index++;
                }
                //没找到就返回-1
                return -1;
            }

            //5.update():修改某个位置的元素
            update(position,data){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                let current = this.head;
                let index = 0;
                while(index++ < position){
                    current = current.next;
                }
                current.data = data;
                return true;
            }

            //6.removeAt(posotion):从链表的特定位置移除一项
            removeAt(position){
                //边界值判定
                if(position < 0 || position >= this.length) return false;

                //分俩步走:1.移除第一项(0)2.移除其它项
                if(position === 0){
                    //移除第一项
                    this.head = this.head.next;
                }else{
                    //移除其它的项
                    let current = this.head;
                    let pre = null;
                    let index = 0;
                    while(index++ < position){
                        pre = current;
                        current = current.next;
                    }
                    pre.next = current.next;
                    return true;
                }

            }

            //10.toString():格式化输出链表
            toString(){
                if(this.length === 0){
                    console.log('链表为空!');
                }else{
                    //定义变量
                    let current = this.head;
                    let linkedStr = '';
                    let index = 0;
                    while(current){
                        linkedStr += current.data + ' ';
                        current = current.next;
                    }
                    return linkedStr;
                }
            }
        }

        //新节点对象
        class Node{
            data = null;
            next = null;
            constructor(data){
                this.data = data;
            }
        }

        //测试代码
        let linkedList = new LinkedList();
        
        //测试append方法
        linkedList.append('aaa');
        linkedList.append('bbb');
        linkedList.append('ccc');
        linkedList.append('ddd');
        linkedList.append('eee');

        console.log(linkedList.toString());
        //测试insert方法
        /* linkedList.insert(1,'aaa');
        console.log(linkedList.toString()); */
        
        //测试get方法
        /* console.log(linkedList.get(0));
        console.log(linkedList.get(3)); */

        //测试indexOf方法
        /* console.log(linkedList.indexOf('aaa'));
        console.log(linkedList.indexOf('eee'));
        console.log(linkedList.indexOf('ccc')); */
    
        //测试update方法
        /* linkedList.update(0,'ggg');
        linkedList.update(4,'vvv');
        linkedList.update(3,'sss');
        console.log(linkedList.toString()); */
    
        //测试removeAt(position)
        /* linkedList.removeAt(0);
        linkedList.removeAt(1);
        linkedList.removeAt(2);
        console.log(linkedList.toString()); */

        //其余方法略...
    </script>
</body>
</html>